package com.wxweven.algorithm.array;

import java.util.HashMap;
import java.util.Map;

class LC220存在重复元素III {

    /*
     * 在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。
     * 如果存在则返回 true，不存在返回 false。
     *
     * 示例 1:
     *
     * 输入: nums = [1,2,3,1], k = 3, t = 0
     * 输出: true
     * 示例 2:
     *
     * 输入: nums = [1,0,1,1], k = 1, t = 2
     * 输出: true
     * 示例 3:
     *
     * 输入: nums = [1,5,9,1,5,9], k = 2, t = 3
     * 输出: false
     *
     * 链接：https://leetcode-cn.com/problems/contains-duplicate-iii
     * 视频讲解：https://www.youtube.com/watch?v=yc4hCFzNNQc
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

        if (nums == null || nums.length == 0 || k <= 0 || t < 0) {
            return false;
        }


        // 先来暴力解法
        // for(int i=0;i<nums.length;i++){
        //     for(int j=i+1; j<=i+k && j<nums.length; j++){
        //         if(Math.abs(Long.valueOf(nums[j])-Long.valueOf(nums[i]))<=t){
        //             return true;
        //         }
        //     }
        // }

        // return false;

        /*
         * nums = [1,5,9,1,5,9], k = 2, t = 3
         *
         * bucket 思想，bucket步长 t+1 = 4
         * 跟重复元素II一样，只维护 k 个 bucket
         *
         * [0, 3]/4, [4, 7]/4, [8, 11]/4
         * 每个数字减去最小值，除以步长，看落到哪个bucket，如果是落到相同的bucket，那肯定是满足条件的
         * 如果落到相邻的bucket(左边或者右边)，那就要检查差值的绝对值是否小于步长
         */

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < min) {
                min = nums[i];
            }
        }

        Map<Long, Integer> bucket = new HashMap<>();

        // 防止 t = 0
        int diff = t + 1;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];

            // 计算当前数字应该落到哪个bucket
            // 用long是防止两数相减后(比如min是负的，int最小值)超过int范围
            long index = (Long.valueOf(num) - Long.valueOf(min)) / diff;

            // check left bucket
            Integer leftBucket = bucket.get(index - 1);
            // 因为上面的diff 加了1，所以这里的只能是小于diff，不能等于
            if (leftBucket != null && Math.abs(Long.valueOf(num) - Long.valueOf(leftBucket)) < diff) {
                return true;
            }

            // check right bucket
            Integer rightBucket = bucket.get(index + 1);
            // 因为上面的diff 加了1，所以这里的只能是小于diff，不能等于
            if (rightBucket != null && Math.abs(Long.valueOf(num) - Long.valueOf(rightBucket)) < diff) {
                return true;
            }

            // 落到统一个bucket，肯定满足条件
            Integer curBucket = bucket.get(index);
            if (curBucket != null) {
                return true;
            }

            bucket.put(index, num);

            // 只维护k个bucket，超过时，要把最前面的删除
            if (i >= k) {
                bucket.remove((Long.valueOf(nums[i - k]) - Long.valueOf(min)) / diff);
            }
        }

        return false;

    }
}